COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00026 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex[106,phy]
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\def\fnc#1{\mathop{\rm #1}\nolimits}
\rm
\line{\sevenrm a63.tex[154,phy] \today\hfill}

\def\circo{{\ooalign
  {\hfil\raise.07ex\hbox{1}\hfil\crcr\mathhexbox20D}}}
\def\circn{{\ooalign
  {\hfil\raise.07ex\hbox{9}\hfil\crcr\mathhexbox20D}}}


\bigskip
\line{\bf Machines and Computations\hfill}

A {\sl device\/} consists of a {\sl carrier\/} set, $C$, of {\sl states\/}
and a {\sl repertory}, which is a set of partial functions
({\sl operations\/}) on~$C$. The domains of the repertory form a boolean
algebra. A~partial identity function in the repertory is called a {\sl test}.
An operation is a subset of $C\times C$, which we abbreviate by writing
$x\mapsto f(x)$ instead of $\{\langle x,f(x)\rangle\}$. A~device also
has a set of {\sl initial\/} states and set of {\sl accepting\/} states, both
subsets of~$C$. (Often there is one initial state, and all states in~$C$
are accepting.)

\vfill\eject

Typical devices; tests are marked with asterisks.
$$\vcenter{\halign{%
#\hfil\qquad
&\hfil#\hfil\qquad
&#\hfil\qquad
&#\hfil\cr
Device&Carrier&Repertory&Definition\cr
\noalign{\smallskip}
Unsigned counter&{\bf N}&{\tt INCREMENT}&$x\mapsto x+1$\cr
\quad Initial state 0&&{\tt DECREMENT}&$x+1\mapsto x$\cr
\quad Accepting states {\bf N}&&{\tt ZERO}$↑{\ast}$&$0\mapsto 0$\cr
&&{\tt NONZERO}$↑{\ast}$&$x+1\mapsto x+1$\cr
&&{\tt DIMINISH}&$x+1\mapsto x$, $0\mapsto 0$\cr
&&{\tt NOOP}&$x\mapsto x$\cr
\noalign{\smallskip}
Stack&$\Sigma↑{\ast}$&{\tt PUSH a}&$x\mapsto xa$\cr
\quad Initial state $\Lambda$&&{\tt POPa}&$xa\mapsto x$\cr
\quad Accepting states $\Sigma↑{\ast}$&&{\tt EMPTY}$↑{\ast}$&$\Lambda\mapsto \Lambda$\cr
&&{\tt TOP}$=a↑{\ast}$&$xa\mapsto xa$\cr
&&{\tt POP ANY}&$x\sigma\mapsto x$\cr
&&{\tt NOOP}&$x\mapsto x$\cr
\noalign{\smallskip}
Signed counter&{\bf Z}&{\tt INCREMENT}&$x\mapsto x+1$\cr
\quad Initial state 0&&{\tt DECREMENT}&$x\mapsto x-1$\cr
\quad Accepting states {\bf Z}&&{\tt ZERO}$↑{\ast}$&$0\mapsto 0$\cr
&&{\tt POSITIVE}$↑{\ast}$&$\{\,\langle x,x\rangle\mid x>0\,\}$\cr
&&{\tt NEGATIVE}$↑{\ast}$&$\{\,\langle x,x\rangle\mid x<0\,\}$\cr
&&{\tt NOOP}&$x\mapsto x$\cr
\noalign{\smallskip}
Finite store&finite $F$&$x←a$&$x\mapsto a$\cr
\quad Initial state ?&&{\tt IF} $x=a↑{\ast}$&$a\mapsto a$\cr
\quad Accepting states $F$&&{\tt IF} $x≠a↑{\ast}$&$\{\,\langle x,x\rangle\mid x≠a\,\}$\cr
\noalign{\smallskip}
Input&$\Sigma↑{\ast}$&{\tt READ} $a$&$ax\mapsto x$\cr
\quad Initial state $x$&&{\tt EOF}$↑{\ast}$&$\Lambda\mapsto \Lambda$\cr
\quad Accepting states $\Sigma↑{\ast}$\cr
Output&$\Sigma↑{\ast}$&{\tt WRITE} $a$&$x\mapsto xa$\cr
\quad Initial state $\Lambda$\cr
\quad Accepting states $\Sigma↑{\ast}$\cr
\noalign{\smallskip}
Control&Finite $Q$&&$i\mapsto j$\cr
\noalign{\smallskip}
Queue&&{\tt APPEND} $a$&$x\mapsto xa$\cr
\quad Initial state $\Lambda$&&{\tt DELETE} $a$&$ax\mapsto x$\cr
\quad Accepting states $\Sigma↑{\ast}$&&{\tt EMPTY}$↑{\ast}$&$\Lambda\mapsto\Lambda$\cr
&&{\tt NONEMPTY}$↑{\ast}$&$\{\langle x,x\rangle,x≠\Lambda\}$\cr
}}$$
A {\sl machine\/} is finite, named, set of devices. That is, it is a
mapping~$\mu$ from a set of names to corresponding devices. Traditionally,
the names are the integers from~1 to~$n$, in which case the machine is
called an $n$-tuple of devices. 
A~{\sl configuration\/} of a machine is a mapping from the names of the
devices to their carriers. The set of configurations is then the cartesian
product of the carriers. If all states in the configuration are initial
(or accepting), the configuration is {\sl initial\/} (or {\sl accepting\/}).

A machine $M$ has an initial mapping, $\alpha↓M$, of input values to
initial configurations, and a {\sl result\/} mapping, $\omega↓M$, of
accepting configurations to output values.

An instruction for a machine is a mapping from device names to an operation
in the repertory of each device. Instructions are partial functions on
configurations. A~configuration~$C$ is in the domain of an instruction~$I$
if, for each device, the state of that device in~$C$ is in the domain of
the corresponding operation in~$I$. If 
$C=\langle x↓1,x↓2,x↓3\rangle$ and
$I=\langle\phi↓1,\phi↓2,\phi↓3\rangle$, then
$I(C)=\langle x↓1\phi↓1,x↓2\phi↓2,x↓3\phi↓3\rangle$,
provided all are defined.

A (deterministic) {\sl program\/} is the union of a finite set of
instructions (with disjoint non-accepting domains). Starting with
an initial configuration~$C↓0$, repeatedly applying a program~$\pi$
gives $C↓i\pi C↓{i+1}$, a~unique finite or infinite sequence of
configurations. The sequence of configurations we call the {\sl history\/}
of the computation; the sequence of instructions applied we call the
{\sl trace\/} (?) of all the computation.

The {\sl transfer function\/} $\phi↓{\pi}$ of a program $\pi$ for
machine~$M$ is $\alpha↓M\pi↑{\ast}\omega↓M$. To be well-defined,
the domains of~$\pi$ and~$\omega↓M$ must be disjoint; this is
simply done, if the machine has a control device, by using in the program
no control operations with accepting states in their domains. States not
in the domain of any control operation are called {\sl halting\/} states.

We say a program {\sl computes\/} a partial function if it has that
function as its transfer function. We say it {\sl accepts\/} the language
that is the domain of its transfer function, and {\sl generates\/} the
language that is the range of its transfer function.
We say a program {\sl recognizes\/} a language if it halts on all input,
and accepts the language.

We say a machine {\sl computes\/} certain functions, or that it {\sl accepts},
{\sl generates}, or {\sl recognizes\/} certain languages, if there are
programs for that machine that do so.

The {\sl graph\/} of a program (actually a multidigraph) has control states
as its vertices. If the control operation of an instruction maps~$i$ to~$j$,
the graph contains an arc from $i$ to~$j$, labeled with all other operations
of the instruction. The initial control state is marked with a double-shafted
arrow in: $\Rightarrow$ \circo. Accepting states are marked with
a double-shafted arrow out: \circn $\Rightarrow$, or by
using $\oplus$ as the state symbol. Every path through the graph
corresponds to a composition of the non-control operations that label it,
and of the control operations corresponding to its arcs.

Machine $M↓1$ {\sl simulates\/} $M↓2$ if they have the same transfer
function. A~partial function~$\rho$ from configurations of $M↓1$ to
configurations of~$M↓2$ is said to be a {\sl representation\/} if it
meets the conditions of the next result, which proves that $M↓1$
simulates~$M↓2$ if certain conditions are met.

\bye
\figbox 2truein:

If:

\display 30pt:$\bullet$:
$\alpha↓2\subseteq \alpha↓1\pi↓1↑{\ast}\rho$
\display 30pt::
(I.e., the initial configuration $x\alpha↓1$ of $\pi↓1$ eventually
becomes a configuration that represents the initial configuration
of~$\pi↓2$.)

\smallskip
\display 30pt:$\bullet$:
$\rho\pi↓2\subseteq \pi↓1↑+\rho$
\display 30pt::
(I.e., if $C↓{1i}$ represents $C↓{2i}$, which advances to $C↓{2(i+1)}$,
then after one or more steps $C↓{1i}$ advances to some $C↓{1(i+1)}$ that 
represents $C↓{2(i+1)}$.)

\smallskip
\display 30pt:$\bullet$:
$\rho\omega↓2\subseteq \pi↓1↑{\ast}\omega↓1$ \quad (This one is buggy.)
\display 30pt::
(I.e., if $C↓{1i}$ represents $C↓{2i}$, accepting, that returns~$y$,
then $C↓{1i}$ eventually becomes an accepting configuration that
returns~$y$.)

Then $\pi↓1$ simulates $\pi↓2$: 
It is clear that if $x\pi↓2y$, the bottom part of the diagram exists,
and induction fills in the top part, so $x\pi↓1y$. The machines are
deterministic, so there is no other~$z$ for which $x\pi↓1z$.

Suppose on input $x$, $\pi↓2$ reaches a rejecting state. So
$C↓{2i}$ rejects, i.e., is not in the domain of~$\omega↓2$. Then if
$C↓{1i}\rho C↓{2i}$, $C↓{1i}$~is not in the domain of~$\rho\omega↓2$.
It is not in the domain of $\pi↓1↑+\omega↓1$, so $\pi↓1$ either runs
forever or reaches a rejecting halt.

Suppose that on input $x$, $\pi↓2$ runs forever. Then corresponding to
an initial segment of $t$~steps of that computation, induction shows
there are at least $t$~steps of a computation by~$\pi↓1$. Therefore
$\pi↓1$ runs forever on input~$x$.

An example of a simulation: 
simulate a counter with initial state~0 using a counter with unspecified
initial state.

\figbox 2truein:

\noindent
The upper part of this diagram shows part of the program $\pi↓2$ and a computation
of~$\pi↓2$, with initial configuration
$\langle$state, counter, input$\rangle =\langle i,0,x\rangle$. Then
$\pi↓2$ has initial configuration $\langle J,a,x\rangle$, where $J$
is a new state, not in $Q↓2$, and $a\in N$. Then the sequence in $\pi↓1↑{a+1}$,
$\langle J→J, {\tt DECR}, {\tt NOOP}\rangle↑a$ followed by
$\langle J→i, {\tt ZERO}, {\tt NOOP}\rangle$ yields the configuration
$\langle i,0,x\rangle$. The programs are otherwise alike,
$\rho$ is the identity function restricted to configurations of~$M↓2$,
and the conditions for simulation are readily shown.
$$\displaylines{\alpha↓2\hbox{: }x\mapsto\langle i,0,x\rangle\cr
\alpha↓1\pi↓1↑{\ast}\rho\hbox{  includes: }x\mapsto\langle J,a,x\rangle\mapsto
\langle J,0,x\rangle\mapstoa \langle i,0,x\rangle\cr}$$
confirming the starting condition. $\rho$, and therefore $\rho\pi↓2$,
is defined only on configurations of~$M↓1$, i.e., not having state $=J$.
On such a configuration~$C$,
$$C\rho\pi↓2=C\pi↓2=C\pi↓1=C\pi↓1\rho\,,$$
so $\rho\pi↓2\subseteq \pi↓1\rho$, comfirming the inductive condition.

Let $C\rho\omega↓2$ be defined. Then $C$ is a configuration of~$M↓2$, and
$C\rho\omega↓2=C\omega↓2$, so $C$ is halted. Then $C\pi↓1↑0\omega↓1=
C\omega↓1=C\omega↓2$, while $C\pi↓1↑+$ is undefined, so 
$C\rho\omega↓2=C\pi↓1↑{\ast}\omega↓1$.
Similarly, if $C\pi↓1↑{\ast}\omega$ is defined, \dots
Oops, this part won't work.

To simulate {\tt NONZERO} using {\tt DECR} and {\tt INCR} on an unsigned
counter,

\figbox 2truein:

\noindent
where $\rho$ is the identity on $Q↓2\times {\bf N}\times\Sigma↑{\ast}$.

To simulate {\tt DIMINISH} using {\tt ZERO} and {\tt DECR}:

\figbox 2truein:

\noindent
where $\rho$ is the identity relation on configuration.

Putting these two simulations together, because the second does not
introduce any {\tt NONZERO} operations, any unsigned counter can be
simulated using an unsigned counter with repertory {\tt INCR}, {\tt DECR},
and {\tt ZERO}.

Any stack may be simulated using a stack without {\tt EMPTY} and with 
$\Lambda$ as is only accepting state. The simulating program starts by pushing
a special symbol,~\#; before halting, it pops the stack until \# is
popped. The function $\rho$ maps $\langle i,z,x\rangle$ into
$\langle i,\#z,x\rangle$ for $i\in Q↓2$.

\figbox 5truein:

\line{\bf Buffering\hfill}

Operations to test stack or input include {\tt POP a} and {\tt SCAN a},
which are destructive. A~machine without the nondestructive operations
${\tt TOP}=a$ and ${\tt NEXT}=a$ can simulate them with the aid of
a finite store called a buffer. We illustrate for input; the details
for stacks are an exercise. The buffer, {\tt buf}, has values
$a$, $b$, $\Lambda$, and~$e$. If {\tt buf} is not~$e$, ${\tt buf}\otimes
{\tt input}↓1$ represents ${\tt input}↓2$. The case ${\tt buf}=e$ represents
${\tt input}↓2=\Lambda$.

\vfill\eject



\figbox 4truein:

\noindent
Notice: that all input is now done by {\tt SCAN}s, and after an {\tt EOF},
the buffer remains $=e$, and no more input operations are done. To make
the machine consume all input before stopping,

\figbox 2truein:

\vfill\eject

To avoid certain counter operation sequences, we can replace

\figbox 2truein:

\noindent
As a result, the sequencs {\tt INCR DECR}, {\tt INCR ZERO}, {\tt ZERO DECR},
and {\tt ZERO ZERO}, are never found in traces of standardized computations.
Blocks of counter operations can then only be {\tt DECR$↑{\ast}$ ZERO
INCR$↑{\ast}$}. The sequence of {\tt INCR$↑{\ast}$} can never be as long
as the number of states in the control, because that can only occur
in a cul-de-sac.

A machine with two unsigned counters can simulate a machine with a
stack, using $\langle x,0\rangle$ to represent the dyadic numeral for~$x$.
(Dyadic numerals are a base-2 positional representation, but the digits
are 1 and~2:
$$\vcenter{\halign{$\hfil #\hfil$&\hfil#\hfil&$\hfil#$\cr
x&&{\rm dyad}\; (x)\cr
\noalign{\smallskip}
0&&\Lambda\cr
1&&1\cr
2&&2\cr
3&&11\cr
4&&12\cr
5&&21\cr
6&&22\cr
7&&111\cr
&etc.\cr}}$$

\vfill\eject

\noindent
To push $\sigma\in\{1,2\}$, change the value $x$ to $2x+1$ or $2x+2$:

\figbox 3truein:

To pop or test for empty stack,

\figbox 3truein:

Obviously then four counters can simulate two stacks simulating a tape
simulating a {\tt RAM}, so a four counter machine can simulate any
collection of memory devices. Amazingly, a two-counter machine can
simulate four counters, using the representation
$\langle 2↑u,3↑v,5↑w,7↑x,0\rangle\rho\langle u,v,w,x\rangle$. It
suffices to simulate four unsigned counters with repertory
{\tt INCR}, {\tt DECR}, {\tt ZERO}.

\figbox 3truein:

$$\displaylines{\langle i,x\rangle\pi↓1\langle j,x+1\rangle\cr
\langle i,2↑x\cdot y\rangle\pi↓2↑+\langle j,2↑{x+1}\cdot y\rangle\cr}$$

\figbox 3truein:

$$\displaylines{\langle i,x+1\rangle\pi↓1\langle j,x\rangle\cr
\langle i,2↑{x+1}\cdot y,0\rangle\pi↓2\langle j,2↑x\cdot y,0\rangle\cr
\langle i,0\rangle\pi↓1\langle k,0\rangle\cr
\langle i,y,0\rangle \pi↓2\langle k,y,0\rangle\cr}$$
Simulating several counters by two, using G\"odel numbers
$2↑x\cdot 3↑u\cdot 5↑v\cdot 7↑w$.

One operation per arc. Replace

\figbox 3truein:

\noindent
Above, domains are disjoint, but

\figbox 3truein:

\noindent
is not. Use instead

\figbox 2truein:


To eliminate multiple operations per instruction, use nondestructive
branching to determine which operations will be done, then do them
sequentially:

\figbox 4truein:

\noindent
States that lead nowhere are combined or deleted by the rules:

\smallskip
\display 20pt::
If there is no path from a starting state to~$q$, delete $q$ from~$Q$
and delete all instructions that include operations with domain~$q$.

\smallskip
\display 20pt::
If there is no path from $q$ to an accepting state, replace $q$ by~$\ominus$,
the rejecting halt, and delete all instructions leaving~$q$.

\vfill\eject

{\tt NOOP}s are eliminated by

\figbox 2truein:

and \qquad is replaced by $\ominus$. 

Watch out: the simulation theorem doesn't work in the above, because the
standardized program is faster than the original. Also, it replaces
some non-halting with halting computations.



\bigskip
\parindent0pt
\copyright 1987 Robert W. Floyd

First draft September 28, 1987

\bye